import org.w3c.dom.ls.LSInput;

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}










class Solution {
    public int[] arr;
    public int size;
    public Solution(int[] nums) {
        this.size=nums.length;
        arr=nums;
    }

    public int[] reset() {
        return arr;
    }

    public int[] shuffle() {
        Random random=new Random();
        int[] arr2=Arrays.copyOf(arr,size);
        for(int i=0;i<size;i++){
            int index=random.nextInt(size-1)+i;
            int tmp=arr2[i];
            arr2[i]=arr2[index];
            arr2[index]=tmp;
        }
        return arr2;
    }
}


















public class project {
    public int totalHammingDistance(int[] nums) {
        int sum=0;
        for(int i=0;i<31;i++){
            int bit=1<<i;
            int count0=0;
            int count1=0;
            for(int j=0;j<nums.length;j++){
                if(bit==(nums[j]&bit)){
                    count1++;
                }else {
                    count0++;
                }
            }
            sum+=count0*count1;
        }

        return sum;
    }


















    public int findMinFibonacciNumbers(int k) {
        int a=1;
        int b=1;
        List<Integer> list=new ArrayList<Integer>();
        list.add(a);
        list.add(b);
        while (a+b<=k){
            list.add(a+b);
            int tmp=a+b;
            a=b;
            b=tmp;
        }
        int count=0;
        for(int i=list.size()-1;i>=0;i--){
            if(list.get(i)<=k){
                count++;
                k-=list.get(i);
            }
        }
        return count;
    }














    public int arrayNesting(int[] nums) {
        int max=0;
        boolean[] booleans=new boolean[nums.length];
        for(int i=0;i<nums.length;i++){
            if(!booleans[i]){
                int index=nums[i];
                int count=0;
                do{
                    index=nums[index];
                    count++;
                    booleans[index]=true;
                }while (index!=nums[i]);
                max=Math.max(count,max);
            }
        }
        return max;
    }
















    public int closedIsland(int[][] grid) {
        int row=grid.length;
        int col=grid[0].length;
        int count=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]==0&&dfs(grid,i,j,row,col)){
                    count++;
                }
            }
        }
        return count;
    }
    public boolean dfs(int[][] arr,int x,int y,int row,int col){
        if(x<0||y<0||x>=row||y>=col){
            return false;
        }
        if(arr[x][y]!=0){
            return true;
        }
        arr[x][y]=1;
        boolean up=dfs(arr,x-1,y,row,col);
        boolean lower=dfs(arr,x+1,y,row,col);
        boolean left=dfs(arr,x,y-1,row,col);
        boolean right=dfs(arr,x,y+1,row,col);
        return up&&lower&&left&&right;
    }

















    public String optimalDivision(int[] nums) {
        int len=nums.length;
        StringBuilder sb=new StringBuilder();
        if(len==1){
            return nums[0]+"";
        }
        if(len==2){
            return nums[0]+"/"+nums[1];
        }
        sb.append(nums[0]).append("/").append("(");
        for(int i=1;i<len-1;i++){
            sb.append(nums[i]).append("/");
        }
        sb.append(nums[len-1]).append(")");
        return sb.toString();
    }



















    public int rob(TreeNode root) {
        Map<TreeNode,Integer> map=new HashMap<>();
        return dfs(root,map);
    }
    public int dfs(TreeNode root,Map<TreeNode,Integer> map){
        if(root==null){
            return 0;
        }
        if(map.containsKey(root)){
            return map.get(root);
        }
        int val=root.val;
        if(root.left!=null){
            val+=(dfs(root.left.left,map)+dfs(root.left.right,map));
        }
        if(root.right!=null){
            val+=(dfs(root.right.left,map)+dfs(root.right.right,map));
        }
        int sum=Math.max(val,dfs(root.left,map)+dfs(root.right,map));
        map.put(root,sum);
        return sum;
    }















    public int maximumGap(int[] nums) {
        Arrays.sort(nums);
        int len=nums.length;
        if(len==0||len==1){
            return 0;
        }
        int cur=1;
        int prev=0;
        int max=0;
        while (cur<len){
            max=Math.max(max,nums[cur]-nums[prev]);
            cur++;
            prev++;
        }
        return max;
    }





















    public String addSpaces(String s, int[] spaces) {
        StringBuilder sb=new StringBuilder();
        int j=0;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(j<spaces.length&&i==spaces[j]){
                j++;
                sb.append(' ');
            }
            sb.append(ch);
        }
        return sb.toString();
    }
















    public int totalMoney(int n) {
        int divisor=n/7;
        int remainder=n%7;
        int money=0;
        int i=0;
        for(i=0;i<divisor;i++){
            for(int j=0;j<7;j++){
                money+=i+j+1;
            }
        }
        if(remainder!=0){
            for(int j=0;j<remainder;j++){
                money+=i+1+j;
            }
        }
        return money;
    }

















    public int removeDuplicates(int[] nums) {
        int len=nums.length;
        if(len==0){
            return 0;
        }
        int prev=1;
        int cur=1;
        while (cur<len){
            if(nums[cur]!=nums[cur-1]){
                nums[prev]=nums[cur];
                prev++;
            }
            cur++;
        }
        return prev;
    }















    public String truncateSentence(String s, int k) {
        String[] str=s.split(" ");
        StringBuilder sb=new StringBuilder();
        for(int i=0;i<k;i++){
            if(i==0){
                sb.append(str[i]);
                sb.append(" ");
            }else{
                sb.append(" ");
                sb.append(str[i]);
            }
        }
        return sb.toString();
    }




















//    public static void main(String args[]) {
//        int i = -5;
//        i = ++(i++);
//        System.out.println(i);
//    }
    public static void main(String[] args){
        Double x=1.2;
        long l = (long) 1.2;
        float f = (float) (x/l);
        System.out.println(f);
    }











    public static void main2(String[]args){
         int a=13;
         a=a/5;
         System.out.println(a);
    }












    public static void main1(String[] args){
        int x = 0;
        int y = 0;
        int k = 0;
        for (int z = 0; z < 5; z++) {
            if ((++x > 2) && (++y > 2) && (k++ > 2)){
                x++;
                ++y;
                k++;
            }
        }
        System.out.println(x + "" +y + "" +k);
    }











    public int sqrt (int x) {
        // write code here
        if(x==0||x==1){
            return x;
        }
        int ret=0;
        int left=0;
        int right=x;
        while (left<right){
            int mid=left+(right-left)/2;
            if((long)mid*mid<x){
                ret=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return ret;
    }



















    public boolean judge (String str) {
        // write code here
        int left=0;
        int right=str.length()-1;
        while (left<right){
            char leftCh=str.charAt(left);
            char rightCh=str.charAt(right);
            if(leftCh!=rightCh){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
